#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>


//struct ListNode* detectCycle(struct ListNode* head) {
//    struct ListNode* fast = head, * slow = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//        {
//            while (head)
//            {
//                if (fast == head)
//                {
//                    return head;
//                }
//                fast = fast->next;
//                head = head->next;
//            }
//        }
//    }
//    return NULL;
//}



//bool hasCycle(struct ListNode* head) {
//    struct ListNode* fast = head, * slow = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//        {
//            return true;
//        }
//    }
//    return false;
//}




//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    int lenA = 0, lenB = 0;
//    struct ListNode* curA = headA, * curB = headB;
//    while (curA->next)
//    {
//        lenA++;
//        curA = curA->next;
//    }
//    while (curB->next)
//    {
//        lenB++;
//        curB = curB->next;
//    }
//    if (curA != curB)
//    {
//        return NULL;
//    }
//    int gap = abs(lenA - lenB);
//    struct ListNode* longlist = headA, * shortlist = headB;
//    if (lenB > lenA)
//    {
//        longlist = headB;
//        shortlist = headA;
//    }
//    while (gap--)
//    {
//        longlist = longlist->next;
//    }
//    while (longlist != shortlist)
//    {
//        longlist = longlist->next;
//        shortlist = shortlist->next;
//    }
//    return longlist;
//}


//class PalindromeList {
//public:
//
//
//    struct ListNode* middleNode(struct ListNode* head) {
//        struct ListNode* slow = head;
//        struct ListNode* fast = head;
//        while (fast && fast->next)
//        {
//            slow = slow->next;
//            fast = fast->next->next;
//        }
//        return slow;
//    }
//
//
//    struct ListNode* reverseList(struct ListNode* head) {
//        struct ListNode* cur = head;
//        struct ListNode* rhead = NULL;
//        while (cur)
//        {
//            struct ListNode* tmp = cur->next;
//            cur->next = rhead;
//            rhead = cur;
//            cur = tmp;
//        }
//        return rhead;
//    }
//
//
//
//    bool chkPalindrome(ListNode* A) {
//        struct ListNode* mid = middleNode(A);
//        struct ListNode* mid_re = reverseList(mid);
//        while (A && mid_re)
//        {
//            if (A->val != mid_re->val)
//            {
//                return false;
//            }
//            A = A->next;
//            mid_re = mid_re->next;
//        }
//        return true;
//    }
//};


//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        struct ListNode* smallhead, * bighead, * smalltail, * bigtail;
//        smallhead = (struct ListNode*)malloc(sizeof(struct ListNode));
//        bighead = (struct ListNode*)malloc(sizeof(struct ListNode));
//        smalltail = smallhead;
//        bigtail = bighead;
//        smallhead->next = bighead->next = NULL;
//        struct ListNode* cur = pHead;
//
//
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                smalltail->next = cur;
//                smalltail = smalltail->next;
//            }
//            else
//            {
//                bigtail->next = cur;
//                bigtail = bigtail->next;
//            }
//            cur = cur->next;
//        }
//
//
//        bigtail->next = NULL;
//        smalltail->next = bighead->next;
//        struct ListNode* newhead = smallhead->next;
//        free(smallhead);
//        free(bighead);
//        return newhead;
//    }
//};
